#include <iostream>

/*
Given str1 and str2, find the minimum window in str1 to cover all characters in str2.

Algorithm:
using two index pointer, to find the first candiadate window, got <start, end> window,
compress the window from start until the condition not valid. then continue to expand 
end to find the next candidate window. do the same thing till find the last candidate window.
*/

using namespace std;

bool FindMinWindow( char* str1, char *str2, int &start, int &end)
{
	int str1Table[256] = {0};
	int str2Table[256] = {0};
	int str1Len = strlen( str1);
	int str2Len = strlen( str2);
	int metCount = 0;
	int min=0x7fffffff, minStart, minEnd;

	start =0;
	end = 0;

	for( int i = 0; i<str2Len; i++ )
	{
		str2Table[str2[i]]++;
	}

	for( end=0; end<str1Len; end++ )
	{
		if( str2Table[str1[end]] == 0 )
			continue;

		str1Table[str1[end]]++;
		if( str1Table[str1[end]] <= str2Table[str1[end]] )
		{
			metCount++;
		}
		if( metCount == str2Len )
		{
			// we get the first candidat, try to compress the window from beginning
			cout<<"candidate "<< start <<" to "<<end<<endl;
			while( start < end )
			{
				if( str1Table[str1[start]] == 0 )
				{
					start++;
					continue;
				}
				if( str1Table[str1[start]] > str2Table[str1[start]] )
				{
					str1Table[str1[start]]--;
					start++;
				}
				else
					break;
			}

			if( end-start+1<min)
			{
				min = end-start+1;
				minStart = start;
				minEnd = end;
			}
			str1Table[str1[start]]--;
			metCount--;
			start++;
		}
	}

	start = minStart;
	end = minEnd;

	return (min<=str1Len)?true:false;
}

int main(void)
{
	char str[]="abbddccamdaaaaabcmd";	
	char uniqueStr[] = "abcd";
	int start = 0;
	int end = 0;

	cout<<"to search "<<uniqueStr<<" in "<<str<<endl;
	if( FindMinWindow( str, uniqueStr, start, end ) )
	{
		cout<<"the min window is from "<<start<<" to "<<end<<endl;
		for( int i=start; i<=end;i++)
		{
			cout<<str[i]<<" ";
		}
		cout<<endl;
	}
	else
	{
		cout<<"Did not find the window to cover all chars"<<endl;
	}

	return getchar();
}